package hwFour1;

import java.util.*;

public class BreadthFirstPaths {

    private final int source;      // 起点顶点
    private final boolean[] marked; // 标记已访问的顶点
    private final int[] edgeTo;     // edgeTo[v] 表示从起点到 v 的路径上的最后一条边
    private final int[] distTo;     // distTo[v] 表示从起点到 v 的最短路径长度

    // 构造函数：以图 G 和起点 s 初始化
    public BreadthFirstPaths(Graph G, int s) {
        this.source = s;
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        distTo = new int[G.V()];
        Arrays.fill(distTo, Integer.MAX_VALUE); // 初始化所有顶点的距离为无穷大
        bfs(G, s); // 执行广度优先搜索
    }

    // 广度优先搜索（BFS）
    private void bfs(Graph G, int s) {
        Queue<Integer> queue = new LinkedList<>();
        marked[s] = true;      // 起点标记为已访问
        distTo[s] = 0;         // 起点到自身的距离为 0
        queue.offer(s);        // 将起点加入队列

        while (!queue.isEmpty()) {
            int v = queue.poll(); // 从队列中取出一个顶点
            for (int w : G.adj(v)) { // 遍历该顶点的所有邻接顶点
                if (!marked[w]) {    // 如果邻接顶点尚未访问
                    marked[w] = true;    // 标记为已访问
                    edgeTo[w] = v;       // 记录路径上的最后一条边
                    distTo[w] = distTo[v] + 1; // 更新最短路径长度
                    queue.offer(w);      // 将邻接顶点加入队列
                }
            }
        }
    }

    // 是否存在从起点到顶点 v 的路径
    public boolean hasPathTo(int v) {
        return marked[v];
    }

    // 返回从起点到顶点 v 的最短路径的长度（常数时间操作）
    public int distTo(int v) {
        return distTo[v];
    }

    // 返回从起点到顶点 v 的路径（如果存在）
    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v)) return null; // 如果没有路径，返回 null
        Stack<Integer> path = new Stack<>();
        for (int x = v; x != source; x = edgeTo[x]) { // 倒序追踪路径
            path.push(x);
        }
        path.push(source);
        return path;
    }

    // 测试代码
    public static void main(String[] args) {
        Graph G = new Graph(6); // 创建一个图，顶点数为 6
        G.addEdge(0, 1);
        G.addEdge(0, 2);
        G.addEdge(0, 5);
        G.addEdge(1, 2);
        G.addEdge(2, 3);
        G.addEdge(2, 4);
        G.addEdge(3, 4);
        G.addEdge(3, 5);

        int source = 0; // 起点
        BreadthFirstPaths bfs = new BreadthFirstPaths(G, source);

        for (int v = 0; v < G.V(); v++) {
            System.out.println("从 " + source + " 到 " + v + " 的最短路径长度: " + bfs.distTo(v));
            System.out.print("路径: ");
            if (bfs.hasPathTo(v)) {
                for (int x : bfs.pathTo(v)) {
                    if (x == source) System.out.print(x);
                    else System.out.print("->" + x);
                }
            }
            System.out.println();
        }
    }
}
